Batch 2 - Class 68 - Pascal Triangle
Preclass Exercise:
- (Geoffrey - 150) Five boys and five girls found five pennies. It was decided to arrange the group in circle, and count out individuals at fixed intervals, giving them a penny as they leave. A clever boy came up with a scheme to arrange the kids in the circle so that all the boys would count out first. The girl standing at the first place, though, insisted that she be allowed to determine the interval, and arranged it so that all girls got counted out first. The arrangement in the circle was as under (Start at 1, and go clockwise). What were the intervals the boy and the girl thought of?
- Answer: Boys 14, Girls 13
Attendance: Anisha, Smiti, Muskaan, Tishyaa, Kushaan, Aryan, Diya, Abhiram, Nandini, Liza, Shubham, Khushi
Class Notes:
- Revisit notion of factorials
- Suppose we write down all 10 bit strings. How many 10 bit strings have exactly 4 zeros?
- Each place can be zero or one. Lets work with smaller numbers and start to tabulate the results
- See if kids recall nCk - if not, explain briefly
- Start with n=0,1,2,3,4,5 and different values of k and start to draw the triangle
.png)
- What are the interesting observations?
- Symmetric - why? nCk=nC(n-k)? Think in terms of placing zeros in a bit string
- What is the sum of entries in each row? 2^n. Why?
- Each number is sum of two "adjacent" numbers in previous row. Why? nCk=(n-1)Ck + (n-1)C(k-1)
- Lets draw this slightly differently and see more patterns
.png)
- Lets look at the pattern along an edge
- First edge 1,1,1,1,1
- Second edge 1,2,3,4,5,6 (counting numbers)
- Third edge 1,3,6,10... - what are these? Triangular numbers (illustrate) What do successive triangular numbers total to? Can you think why?
- Fourth edge 1,4,10,20,35... - what are these? Tetrahedral numbers (illustrate)
- Fifth edge 1,5,15,35,70... - can you guess what might these be? Yes, pentatope numbers - number of vertices in a 4-D "triangle"
- Hockey Stick Pattern - Example 1+3+6+10+15 = 35 - Why?
- Parallelogram Pattern - Example - the whole block from left top to 21, totals to 84 - Why? Successive Hockey sticks!
- Lets try one more way of drawing it
.png)
- What are the diagonal totals? Does anyone recognize these numbers? Can you think why?
- Can you spot them on the original Pascal triangle?
- There are several other advanced patterns hidden in Pascal triangle - such as value of e, pi, star of david, catalan numbers...
Homework
- (Geoffrey - 161 Modified) The sketch below shows the plan of industrial establishment with secret weapons. There are only three gates which are guarded. There is some information leakage, and they found this note supposedly written for the spy
"Meet me every tuesday at the corner near my office. Enter by northwest gate and take a different route each time. That gives you 210 choices".
The detectives presumed the spy would enter top left and would always move to the right or down, in order to be efficient. Which office occupant was leaking the information?
.png)
- Answer: this is same as ways of arranging a number of 1's in a bit string. Since 210 appears as 5th number in 11th row, it must be at intersection of 7th and 5th Street (there is only one such combination above - if it was a larger grid, there would be two possibilities)
References:
A Decade of the Berkeley Math Circle. The American Experience, Volume 1. Zvezdelina Stankova, Tom Rike
Mathematical Puzzles, Geoffrey Mott-Smith